题目
https://leetcode-cn.com/problems/number-of-islands/
题解
DFS
- 基础DFS题
class Solution {
public:
void dfs(vector<vector<char>>& grid,int i ,int j)
{
if(i<0 || i >= grid.size() || j<0 || j >= grid[0].size() || grid[i][j]=='0') return;
//通过将'1'改为'0'来说明该位置已经被遍历过
grid[i][j] = '0';
dfs(grid,i-1,j);
dfs(grid,i+1,j);
dfs(grid,i,j-1);
dfs(grid,i,j+1);
}
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
int n = grid[0].size();
int res = 0;
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
if(grid[i][j] == '1')
{
dfs(grid,i,j);
res++;
}
}
}
return res;
}
};
- 时间复杂度:$O(MN)$
- 空间复杂度:$O(MN)$
BFS
- 基础BFS题
class Solution {
public:
bool isIsland(vector<vector<char>>& grid,int i ,int j)
{
if(i<0 || i >= grid.size() || j < 0 || j>= grid[0].size() || grid[i][j] == '0' ) return false;
grid[i][j] = '0';
return true;
}
int numIslands(vector<vector<char>>& grid) {
int res = 0;
int m = grid.size();
int n = grid[0].size();
queue<pair<int,int>> q;
for(int i = 0; i <m;++i)
{
for(int j = 0; j < n;++j)
{
if(grid[i][j] == '1' )
{
q.push(make_pair(i,j));
res++;
}
while(!q.empty())
{
pair<int,int> p = q.front();
q.pop();
int x = p.first;
int y = p.second;
if(isIsland(grid,x+1,y)) q.push(make_pair(x+1,y));
if(isIsland(grid,x-1,y)) q.push(make_pair(x-1,y));
if(isIsland(grid,x,y+1)) q.push(make_pair(x,y+1));
if(isIsland(grid,x,y-1)) q.push(make_pair(x,y-1));
}
}
}
return res++;
}
};
- 时间复杂度:$O(MN)$
- 空间复杂度:$O(???)$
这个的空间复杂度有歧义，leetcode官方的答案写的是O(min(M,N)),我认为是O(max(m,n))
x x x [1]
x x [1] 1
[1] [1] 1 1
x为已经遍历的位置,[1]为在队列里的位置
但是看了这个帖子，时间复杂度应该是O(MN)
PS:基本没人问这个问题，也没什么人提，一堆人刷题从来不管空间复杂度，时间复杂度的。。。。
并查集
简单的并查集学习
看了这篇文章做的这个题，感觉写的太复杂了，将并查集扩展到了2维
class Solution { public: void Init(vector<vector<pair<int,int>>> &v,vector<vector<int>>& rank,int m,int n) { for(int i = 0; i < m ;++i) { for(int j = 0; j < n; ++j) { v[i][j] = make_pair(i,j); rank[i][j] = 1; } } } pair<int,int> Find(vector<vector<pair<int,int>>> &v,pair<int,int> x) { int a = x.first; int b = x.second; return x == v[a][b] ? x : (v[a][b] = Find(v,v[a][b])); } void Merge(vector<vector<pair<int,int>>> &v,vector<vector<int>>& rank,pair<int,int> i,pair<int,int> j) { pair<int,int> x = Find(v,i), y = Find(v,j); int a = x.first; int b = x.second; int c = y.first; int d = y.second; if (rank[a][b] <= rank[c][d]) v[a][b] = y; else v[c][d] = x; if (rank[a][b] == rank[c][d] && x != y) rank[c][d]++; } int numIslands(vector<vector<char>>& grid) { int m = grid.size(); int n = grid[0].size(); vector<vector<pair<int,int>>> v(m,vector<pair<int,int>>(n,make_pair<int,int>(0,0))); vector<vector<int>> rank(m,vector<int>(n,0)); Init(v,rank,m,n); for(int i = 0;i <m;++i) { for(int j = 0; j < n; ++j) { if(grid[i][j] == '1') { if(i-1>=0 && grid[i-1][j] == '1') Merge(v,rank,make_pair(i-1,j),make_pair(i,j)); if(i+1<m && grid[i+1][j] == '1') Merge(v,rank,make_pair(i+1,j),make_pair(i,j)); if(j-1>=0 && grid[i][j-1] == '1') Merge(v,rank,make_pair(i,j-1),make_pair(i,j)); if(j+1<n && grid[i][j+1] == '1') Merge(v,rank,make_pair(i,j+1),make_pair(i,j)); } } } set<pair<int,int>> s; for(int i = 0; i < m; ++i) { for(int j = 0; j < n;++j) { if(grid[i][j] == '1') s.insert(Find(v,make_pair(i,j))); } } return s.size(); } };
- 时间复杂度：T T
不太懂，证明可以看算法导论，我这里直接拉一下leetcode上的说明
时间复杂度：$O(MN * \alpha(MN))$，其中 M 和 N 分别为行数和列数。注意当使用路径压缩（见 find 函数）和按秩合并（见数组 rank）实现并查集时，单次操作的时间复杂度为 $\alpha(MN)$，其中 $\alpha(x)$ 为反阿克曼函数，当自变量 x 的值在人类可观测的范围内（宇宙中粒子的数量）时，函数 $\alpha(x)$的值不会超过 5，因此也可以看成是常数时间复杂度。
- 空间复杂度：$O(MN)$
- 写法简化版本
```cpp
```